<html xmlns:v="urn:schemas-microsoft-com:vml" 
xmlns:o="urn:schemas-microsoft-com:office:office" 
xmlns:w="urn:schemas-microsoft-com:office:word" 
xmlns:st1="urn:schemas-microsoft-com:office:smarttags" 
xmlns="http://www.w3.org/TR/REC-html40"><head>


<meta http-equiv="Content-Type" content="text/html; 
charset=windows-1252">
<meta name="ProgId" content="Word.Document">
<meta name="Generator" content="Microsoft Word 10">
<meta name="Originator" content="Microsoft Word 10">
<link rel="File-List" 
href="http://uva.onlinejudge.org/external/103/p6_files/filelist.xml">
<link rel="Edit-Time-Data" 
href="http://uva.onlinejudge.org/external/103/p6_files/editdata.mso">
<!--[if !mso]>
<style>
v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style>
<![endif]-->
<title>Problem G - September 2002 Monthly Contest</title>
<o:smarttagtype 
namespaceuri="urn:schemas-microsoft-com:office:smarttags" name="place"></o:smarttagtype>
<o:smarttagtype 
namespaceuri="urn:schemas-microsoft-com:office:smarttags" 
name="PlaceName"></o:smarttagtype>
<o:smarttagtype 
namespaceuri="urn:schemas-microsoft-com:office:smarttags" 
name="PlaceType"></o:smarttagtype>
<!--[if gte mso 9]><xml>
 <o:DocumentProperties>
  <o:Author>Shahriar Manzoor</o:Author>
  <o:LastAuthor>Shahriar Manzoor</o:LastAuthor>
  <o:Revision>33</o:Revision>
  <o:TotalTime>32</o:TotalTime>
  <o:LastPrinted>2002-09-09T07:46:00Z</o:LastPrinted>
  <o:Created>2002-07-24T06:14:00Z</o:Created>
  <o:LastSaved>2002-09-09T07:48:00Z</o:LastSaved>
  <o:Pages>1</o:Pages>
  <o:Words>114</o:Words>
  <o:Characters>653</o:Characters>
  <o:Company>BUET</o:Company>
  <o:Lines>5</o:Lines>
  <o:Paragraphs>1</o:Paragraphs>
  <o:CharactersWithSpaces>766</o:CharactersWithSpaces>
  <o:Version>10.2625</o:Version>
 </o:DocumentProperties>
</xml><![endif]--><!--[if gte mso 9]><xml>
 <w:WordDocument>
  <w:View>Print</w:View>
  <w:Zoom>BestFit</w:Zoom>
  <w:GrammarState>Clean</w:GrammarState>
  <w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel>
 </w:WordDocument>
</xml><![endif]--><!--[if !mso]><object
 classid="clsid:38481807-CA0E-42D2-BF39-B33AF135CC4D" id=ieooui></object>
<style>
st1\:*{behavior:url(#ieooui) }
</style>
<![endif]-->
<style>
<!--
 /* Style Definitions */
 p.MsoNormal, li.MsoNormal, div.MsoNormal
	{mso-style-parent:"";
	margin:0in;
	margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	font-size:12.0pt;
	font-family:"Times New Roman";
	mso-fareast-font-family:"Times New Roman";}
h2
	{mso-style-next:Normal;
	margin-top:12.0pt;
	margin-right:0in;
	margin-bottom:3.0pt;
	margin-left:0in;
	mso-pagination:widow-orphan;
	page-break-after:avoid;
	mso-outline-level:2;
	font-size:14.0pt;
	font-family:Arial;
	font-weight:bold;
	font-style:italic;}
p
	{mso-margin-top-alt:auto;
	margin-right:0in;
	mso-margin-bottom-alt:auto;
	margin-left:0in;
	mso-pagination:widow-orphan;
	font-size:12.0pt;
	font-family:"Times New Roman";
	mso-fareast-font-family:"Times New Roman";}
pre
	{margin:0in;
	margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	tab-stops:45.8pt 91.6pt 137.4pt 183.2pt 229.0pt 274.8pt 320.6pt 366.4pt 412.2pt 458.0pt 503.8pt 549.6pt 595.4pt 641.2pt 687.0pt 732.8pt;
	font-size:10.0pt;
	font-family:"Courier New";
	mso-fareast-font-family:"Times New Roman";}
@page Section1
	{size:8.5in 11.0in;
	margin:1.0in 1.0in 1.0in 1.0in;
	mso-header-margin:.5in;
	mso-footer-margin:.5in;
	mso-paper-source:0;}
div.Section1
	{page:Section1;}
-->
</style>
<!--[if gte mso 10]>
<style>
 /* Style Definitions */
 table.MsoNormalTable
	{mso-style-name:"Table Normal";
	mso-tstyle-rowband-size:0;
	mso-tstyle-colband-size:0;
	mso-style-noshow:yes;
	mso-style-parent:"";
	mso-padding-alt:0in 5.4pt 0in 5.4pt;
	mso-para-margin:0in;
	mso-para-margin-bottom:.0001pt;
	mso-pagination:widow-orphan;
	font-size:10.0pt;
	font-family:"Times New Roman";}
</style>
<![endif]--><!--[if gte mso 9]><xml>
 <o:shapedefaults v:ext="edit" spidmax="4098"/>
</xml><![endif]--><!--[if gte mso 9]><xml>
 <o:shapelayout v:ext="edit">
  <o:idmap v:ext="edit" data="1"/>
 </o:shapelayout></xml><![endif]-->
</head><body style="" lang="EN-US">

<div class="Section1">

<p class="MsoNormal" style="text-align: center;" align="center"><b 
style=""><span style="font-size: 18pt; color: black;">Problem G<o:p></o:p></span></b></p>

<p class="MsoNormal" style="text-align: center;" align="center"><b 
style=""><span style="font-size: 24pt; color: black;">Tiling</span></b><b
 style=""><span style="color: black;"><o:p></o:p></span></b></p>

<p class="MsoNormal" style="text-align: center;" align="center"><b><span
 style="color: black;">Input: </span></b><span style="color: black;">standard
 input<o:p></o:p></span></p>

<p class="MsoNormal" style="text-align: center;" align="center"><b><span
 style="color: black;">Output: </span></b><span style="color: black;">standard
output<o:p></o:p></span></p>

<p class="MsoNormal" style="text-align: center;" align="center"><b><span
 style="color: black;">Time Limit:</span></b><span style="color: black;">
 2 seconds<o:p></o:p></span></p>

<p class="MsoNormal" style="text-align: center;" align="center"><b 
style=""><span style="color: black;">Memory Limit: </span></b><span 
style="color: black;">32 MB<o:p></o:p></span></p>

<p class="MsoNormal" style="text-align: center;" align="center"><span 
style="color: black;"><o:p>&nbsp;</o:p></span></p>

<p class="MsoNormal" style="text-align: justify;">In how many ways can 
you tile a
2x<em>n</em> rectangle by 2x1 or 2x2 tiles? </p>
<center>
<p style="text-align: justify;">Here is a sample tiling of a 2x17 
rectangle. </p>
<img src="acm-10359_files/p10359.gif">
</center>
<p style="text-align: justify;"><b style=""><span style="font-size: 
18pt;">Input and Output<o:p></o:p></span></b></p>

<p style="text-align: justify;">Input is a sequence of lines, each line
containing an integer number <em>0 &lt;= n &lt;= 250</em>. For each line
 of
input, output one integer number in a separate line giving the number of
possible tilings of a 2x<em>n</em> rectangle. </p>

<p class="MsoNormal" style="text-align: justify;"><b style=""><span 
style="font-size: 18pt;">Sample Input<o:p></o:p></span></b></p>

<pre><span style="font-size: 11pt;">2<o:p></o:p></span></pre><pre><span style="font-size: 11pt;">8<o:p></o:p></span></pre><pre><span style="font-size: 11pt;">12<o:p></o:p></span></pre><pre><span style="font-size: 11pt;">100<o:p></o:p></span></pre>

<p class="MsoNormal" style="text-align: justify;"><span 
style="font-size: 11pt; font-family: &quot;Courier New&quot;;">200<o:p></o:p></span></p>

<p class="MsoNormal" style="text-align: justify;"><o:p>&nbsp;</o:p></p>

<p class="MsoNormal" style="text-align: justify;"><b style=""><span 
style="font-size: 18pt;">Sample
Output<o:p></o:p></span></b></p>

<pre><span style="font-size: 11pt;">3<o:p></o:p></span></pre><pre><span style="font-size: 11pt;">171<o:p></o:p></span></pre><pre><span style="font-size: 11pt;">2731<o:p></o:p></span></pre><pre><span style="font-size: 11pt;">845100400152152934331135470251<o:p></o:p></span></pre><pre><span style="font-size: 11pt;">1071292029505993517027974728227441735014801995855195223534251<o:p></o:p></span></pre>

<div class="MsoNormal" style="text-align: center;" align="center">

<hr align="center" size="2" width="100%">

</div>

<p class="MsoNormal" style=""><st1:place><st1:placetype><b style="">University</b></st1:placetype><b
 style=""> of </b><st1:placename><b style="">Alberta</b></st1:placename></st1:place><b
 style=""> Local Contest<o:p></o:p></b></p>

</div>

</body></html>